1. Field of the Invention
The present invention generally relates to a method of labelling polygons during integrated circuit network analysis. More specifically, the present invention relates to the analysis of an integrated circuit layout.
2. State of the Art
Integrated circuit analysis is often performed for verifying whether integrated circuit design rules have been followed and an integrated circuit correctly implemented. Design rules are utilized during a chip design process to insure that the integrated circuit layout designs are functional and capable of manufacture. For example, the design rules may prohibit a circuit layout from being designed with short circuits among the chip's layers. Integrated circuit analysis is also performed to verify that the electrical interconnections of a semiconductor chip correspond to an originally intended design once it has been determined that the design rules have been followed correctly (i.e., connectivity analysis).
Integrated circuit analysis for design rule checking and/or connectivity analysis is performed by examining the physical circuit layout geometry of a semiconductor integrated circuit which is to be, or has been, fabricated during a computer controlled process (e.g., a lithography process using optical methods or an electron beam machine). During this examination of the circuit layout for a chip, an actual netlist is generated which represents the interconnections of all elements on the chip.
To perform a check of a chip layout's functionality or electrical connectivity, or to ensure that the design rules have been followed, a circuit geometry is analyzed to extract an actual netlist for comparison with a netlist representative of the desired electrical connectivity. If the actual netlist generated during the circuit analysis does not agree with the desired netlist, it is likely that an error exists in the computer software for constructing the layout.
Integrated circuit analysis for connectivity analysis is also useful to verify that important interconnections on a chip are still present following human interaction with the design of the chip. For example, a designer must draw a circuit layout geometry to match the desired netlist. In addition, the designer will often make minor adjustments to the layout of a chip following the original design. It is therefore important that the completed chip be examined to verify that the actual netlist associated with the chip corresponds to the originally intended netlist.
Such a qualification of the connectivity of the chip is important when, for example, a manufacturer has been hired to produce chips having a requested design. Integrated circuit analysis is used in this case to verify that the designer has produced a circuit layout which complies with the pre-established design specifications requested. In this regard, integrated circuit analysis can also be used to, for example, verify the specific spacing between two layers of the chip's circuit layout, and so forth.
The integrated circuit analysis of a chip layout is preferably performed prior to actual manufacturing of the chip because such an analysis is relatively cost-effective. However, a similar analysis could be performed on a chip layout after it has been manufactured to verify the connectivity of the circuit components on the completed chip.
With integrated circuit layout analysis, it is often necessary to differentiate between portions of the circuit layout which are on the same electrical node from portions of the circuit layout which are not on the same electrical node. An electrical node is an area or zone of electrical contact on the circuit layout. Such a differentiation is achieved during integrated circuit analysis by examining the chip's circuit layout, wherein the components of the circuit layout appear as a number of polygonal shapes. Each polygon represents an electrical node, such that components which form a particular polygon are part of the same electrical node.
A polygon is a region bounded by some number of edges, no two of which intersect at any point other than their endpoints. Each polygon may be represented by breaking it down into a number of objects, for example edges, which are stored in an input file. For example, referring to FIG. 1, an integrated circuit layout for a semiconductor chip SC is shown. The circuit layout shown in FIG. 1 includes two polygons labelled A and B which form two separate electrical nodes on the chip layer shown. The polygon labelled A has been broken down for the purposes of integrated circuit analysis into the objects "1" through "5", while the polygon labelled B has been broken down into the objects "6" to "7".
During the integrated circuit analysis of a chip or chip layout, design rule checking and/or connectivity analysis is performed by determining the interrelationships of the objects in the circuit layout. Accordingly, each of the objects which appear in the circuit layout is detected during the integrated circuit analysis. To determine the interrelationship of the objects, it is desirable to correlate an identifying mark with all of the objects that are a part of the same polygon and thus, part of the same electrical node. Although the form of the identifying mark is arbitrary (for example, a number), it must be unique for each polygon.
For example, as shown in FIG. 2, the input file for the FIG. 1 circuit layout might consist of data which identifies the edges of each of the objects 1-7. Because the memory space required to store the interrelationships of the object edges could be great, which is particularly true for a large integrated circuit, this information is not included in the input file. Rather, integrated circuit analysis is used to determine the outer boundaries of the objects which together define the outer boundaries of the polygons A and B.
An analysis of the integrated circuit shown in FIG. 1 would result in the production of an output file containing data corresponding to the interrelationships of the objects (for example, object edges) which form the polygons A and B, as shown in FIG. 3. As can be seen in FIG. 3, the integrated circuit analysis of the FIG. 1 circuit using the information stored in the input file provides a reconciliation of the object edges which intersect or overlap to form a single polygon.
The first step of integrated circuit analysis then involves separately labelling the individual objects which compose the polygons of the circuit layout by assigning a number, letter or other identifying feature to each of the objects. A goal of integrated circuit analysis is to permit the direct determination of connectivity within the circuit layout even though the objects do not touch at the point on the circuit layout currently being examined. In other words, the goal is to assign identifiers (e.g., numbers) to the various objects such that if two object identifiers are equivalent, the objects can be considered to be part of the same polygon, and thus part of the same electrical node.
Because the layer of a semiconductor chip is two-dimensional, a two-dimensional traversal process can be effectively used to achieve this goal. Almost all two-dimensional traversal methods used for integrated circuit analysis utilize scan line methods. Tree or other hierarchical region-oriented query methods either involve too much overhead (i.e., excessive memory space and processing time is associated with the query method) or require that substantially all design data associated with the circuit layout be placed into memory. Although storing all of the design data may work for smaller circuit layouts, it would not be feasible for larger designs. Since circuit layout analysis often requires a flattened representation of the data, this latter requirement renders the use of tree or region-oriented query methods impractical.
On the other hand, a scan line which is passed over an integrated circuit layout is able to detect all of the objects in the layout that happen to touch or cross the scan line at any given time. Thus, the scan line can be used to detect actual geometric data regarding the interrelationship of the objects on an integrated circuit layout which currently contact the scan line. By accumulating or storing information about previous scan lines, global information can be constructed.
Known two-dimensional traversal methods typically sort the design data to be gathered by the scan line into some order for analysis. For example, all points which form a portion of the circuit layout (e.g., a polygon) can, when viewed on a two-dimensional plane, be represented by an X and a Y value. Similarly, all edges or objects which form part of a polygon can be represented by sets of X and Y values. Accordingly, one example of a sorting criterion would be to sort detected data or information (e.g., data corresponding to the edge of an object forming part of a polygon) first by the lower X value of the data and then by the lower Y value of the data.
To implement a scan line traversal, a scan line is passed over the plane which includes the circuit layout. Only the objects that touch or intersect the scan line at a given time are kept in memory, ordered along the scan line in accordance with the selected sorting criterion. The scan line is traversed from an initial scan line coordinate value to the next point where an "event" occurs. At the least, an "event" is defined as a scanned point at which data is to be stored, such as the beginning or ending of an object.
For example, as shown in FIG. 1, a vertical scan line which is parallel to the Y axis and having a selected X coordinate is traversed from an initial Y value to the next Y value where an "event" occurs (such as the initial encounter of an object edge). At this latter Y value, data is obtained from the circuit layout by analyzing the scan line for all points or objects which contact the scan line, beginning with the object in the scan line having the lowest Y value. The vertical scan line is then moved to the next X coordinate value and the process repeated in the Y direction.
Accordingly, if during the traversal of a particular scan line in the Y direction, the beginning of an object is encountered (e.g., the lower left hand corner of an object which forms a part of a polygon), data related to the occurrence of that event will be stored. Some scan line methods, particularly object merging and overlap removal methods, also mark events and store data at any intersection between two objects, even if they do not occur at the ends of the objects.
When labelling polygons, a temporary number is assigned when an object is first noticed by the scan line, and this temporary number is updated when necessary. This updating occurs, for example, when two objects with different numbers touch at some point, as is the case when the two objects form part of the same polygon. Such updating is necessary if, as mentioned above, all objects which form part of the same polygon are to be commonly labelled.
For example, the decimal numbers in each object of FIG. 1 represent the order in which they are read from the FIG. 2 input file as the scan line passes across the circuit layout. For this reason, the temporary numbers assigned can be considered canonical members. As noted above, the memory space required for storing the shapes (e.g., the edges) of the various objects is relatively small such that the expense of preparing the FIG. 2 input file is minimal. However, because the memory requirements for storing the interrelationships of the various objects in a circuit layout are relatively large and costly, this information is not included in the input file. Rather, as mentioned above, this information is derived using a labelling scheme as will now be described more fully.
Referring again to FIG. 1, the lower case letters represent the temporary "numbers" used to identify an object before the object is written to an output file. In FIG. 1, the series of parallel, vertical lines numbered 1 through 9 correspond to the various X locations of the vertical scan line at which data regarding the circuit layout is stored for later production of an output file.
During the integrated circuit analysis of the circuit layout shown in FIG. 1, the scan line number 1 corresponds to the detection of the left edge of the object 1. Accordingly, the object 1 of the left-most polygon A is read from the input file first. Since none of the temporary object numbers have been assigned, this first object is assigned a "number" represented by the letter "a". The object number 2 is read next, and since it does not touch the object 1 directly, a new number (i.e., the letter "b") is assigned. A similar assignment of a new number "c" occurs when the object 3 is first encountered by the scan line as it moves across the FIG. 1 circuit layout.
When the fourth scan line, as shown in FIG. 1, is processed, it is immediately recognized that the object 4 contacts the object 2. Accordingly, the temporary number for the object 2 (i.e., the letter "b") is given to the object 4. With further processing along the fourth vertical scan line, it is found that the object 3 also contacts the object 4, but that it has a different temporary number (i.e., the letter "c"). As a result, data must be stored to indicate that the temporary number for the object 3 or the object 4 (or both) must be changed since the goal is to commonly number all objects which are in contact with one another.
Thus far, the only objects affected have been those located within the vertical scan line currently being processed. Accordingly, the temporary numbers of the objects encountered up to this point in the FIG. 1 circuit layout could be easily assigned or updated by the storage of a relatively small amount of information.
However, a different situation occurs when, for example, the object 5 is encountered by the fifth scan line and is found to contact the objects 1 and 4. In this case, the objects 2 and 3 are no longer in the scan line. Accordingly, excess memory space is required to store information regarding the complete circuit layout so that the number assigned to the object 5 will be assigned not only to the objects 1 and 4, but to the objects 2 and 3 as well.
One existing method for labelling polygons to accommodate this situation involves storing all of the objects for a given polygon in memory during a scan line pass. With this method, all of the objects for each polygon are saved in memory until the entire polygon has been passed (e.g., information regarding all of the objects 1-5 with respect to the polygon A and information regarding the objects 6-7 with respect to polygon B of FIG. 1). At this time a common number, or label, is assigned to all of the contacting objects, and all of the objects are written to the output file. This method is described by Franco Preparata and Jurg Nievergelt in "Plane-Sweep Algorithms for Intersecting Geometric Figures," Communications of the ACM 25(10), pp. 739-747, Oct. 1982.
However, the largest polygons will typically cover a large fraction of the circuit layout design area. Furthermore, the size of a list of the objects can be much greater than the amount of memory available. Accordingly, this method is not feasible except for very small design areas and/or polygons.
A second existing method for labelling polygons involves saving global topology information in memory. In this method only the object merging information is saved in memory during a first scan line pass of the integrated circuit layout. Such merging information would include, for example, information regarding objects which have been determined to be in contact with one another during the first scan line pass (e.g., information regarding the contact between objects 1 and 5, objects 2 and 4, objects 3 and 4, and objects 4 and 5 of FIG. 1). Afterwards, some processing is performed to reconcile all of the merge operations, and this information is then used to name, or label, the polygons during a second pass of the scan line over the circuit layout.
In a pathological case such as that shown in FIG. 4, this can require O(n) space, and the reconciliation can require O(n) to O(n.sup.2) time, where n is the number of edges in the integrated circuit network. More specifically, assume a scan line parallel to the X axis (i.e., a horizontal scan line) is passed from the bottom to the top of the circuit layout shown in FIG. 4. Since each downward-extending tab shown in FIG. 4 initially appears to be a separate object during such a scan of the circuit layout, the number of merge events can approach the number of objects in the input data file.
That is, all of the tabs in the rows marked b and d of FIG. 4 must eventually be merged with the remainder of the polygon. Since the number of edges in the tabs is arbitrary, it is not feasible to keep them all in memory awaiting resolution. The rows marked c and e will not, however, require any merge information as all of the edges in these rows are immediately recognized via the horizontal scan line as being part of the same overall polygon.
In the FIG. 4 example, the number of merge events will therefore approach one half of the object count. If, on the other hand, there were no tabs extending upwards in the FIG. 4 polygon, the event count could near the object count. This latter example is topologically similar to a polygon which represents a typical power supply node. Global topology methods similar to that mentioned herein are described by Henry S. Baird in "Fast Algorithms for LSI Artwork Analysis," Journal of Design Automation and Fault-Tolerant Computing, 2(2), pp. 179-209 (1978); paul Losleben and Kathryn Thompson, "Topological Analysis for VLSI Circuits," Proceedings of the 16th Design Automation Conference, pp. 461-473 (1979); Takashi Mitsuhashi, Toshiaki Chiba, Makato Takashima, and Kenji Yoshida in "An Integrated Mask Artwork Analysis System," Proceedings of the 17th Design Automation Conference, pp. 277-284 (1980); and David Noice, John Newkirk, and Rob Mathews in "A Polygon Package for Analyzing Integrated Circuit Designs," VSLI Design 2(3), pp. 33-36 ( 1981).
A third method of labelling polygons to accommodate the aforementioned object number updating situation involves writing all information, such as polygon start, object merging and polygon end information, into a temporary file. This method was first described by Szymanski and Van Wyk, (see, for example, Thomas G. Szymanski, "Space Efficient Algorithms for VLSI Artwork Analysis," Proceedings of the 20th Design Automation Conference, IEEE (1983)). With this method, two passes are made through the data contained on the circuit layout: a first pass of a scan line over the circuit layout to determine which objects contact each other (the scanning phase), and a second backward pass through the data representing the circuit layout to determine the final object numbers (the renaming phase).
In the first scanning phase, objects are read from the input file and temporary object numbers are assigned to each separate object (or edge) encountered by the scan line. The temporary numbers are stored with objects in a temporary file when the objects are scanned during the first pass. The temporary file includes control information mixed with output objects (or edges) that have been assigned temporary numbers. Every time an event occurs, a record of that event is written to the temporary file. In this method, an event is defined as:
1. The beginning of a polygon (i.e., the beginning of an electrical node) which, for example corresponds to the initial detection of an object boundary line which does not contact other previously detected objects; such a detection corresponds to the assignment of a new canonical number. PA1 2. The ending of a polygon (i.e., the ending of an electrical node) which, for example, corresponds to the detection of another boundary line for a previously detected object, wherein the object boundary line is not in contact with any other objects. An event which corresponds to the detection of an end of a polygon (e.g. the top of a polygon when a horizontal scan line is used) results in the release of a canonical number such that it can be later used for a different polygon. PA1 3. The merging of one object associated with a polygon or an electrical node into another object originally associated with a different polygon or electrical node. PA1 4. The end of an input object. Such an event may have one of the previously listed events associated with it as well, such as a merge or an end of polygon event. The canonical number of the input object as determined during the first pass of the scan line is saved with the object in the temporary file. PA1 1. When an end-of-node marker is found with an object in the temporary file, the canonical number the object references is set aside and a final name (thus this is the "renaming" phase) is assigned; this final name will be associated with each object that is determined to reference that canonical number during the backward pass, indicating that it is part of the same polygon. PA1 2. When a merge-objects marker is found with an object read from the temporary file, one of the two merging objects is considered to be the winner and the other object is considered to be the loser; the winner object is normally the object which appears first in the temporary file during the backward pass through the temporary file. The canonical number of the object which is considered to be the loser object is updated with the final name associated with the object considered to be the winner. PA1 3. When a beginning-of-node marker is found with the object read from the temporary file, the canonical number is released (for later reuse, if necessary) thus indicating the end of the polygon. PA1 4. When an object is encountered, its final name is assigned according to its canonical number, as saved during the first scan line pass. This object and its associated control information is then written to the output file and recorded therein. PA1 scanning the geometric layout during a first scan line pass; PA1 processing the scan line at each occurrence of an event to detect objects which contact the scan line; PA1 assigning temporary numbers and root designators to the objects which contact the scan line in accordance with a sorting criterion; PA1 updating the temporary numbers assigned to the objects to keep the temporary number associated with the earliest root designator of each separately detected polygon; and, PA1 renaming each object which forms a part of the same polygon with a common label, said step of updating including the steps of:
Storing the events that occur during the scanning phase allows the reconstruction of the state of the scan line during the renaming phase. During the renaming phase, the temporary file is read in reverse order during a backward pass through the circuit layout to take advantage of the information gathered. In this regard, the following rules of reconstruction are followed to rename the polygons:
The information is thus stored in a forward order during the first pass, and is read in a reverse order during the second pass. The output file is written in reverse order as well. Accordingly, either an additional pass through the output file is required to reverse the data once again for outputting the data in proper order, or the output file must be allocated in full and then written in reverse order.
For example, considering an analysis of the FIG. 1 circuit layout in general, an input file might list all of the objects 1 through 7 as shown in FIG. 2. During the aforedescribed first scan line pass of the circuit layout, a temporary file might be produced which includes temporary object numbers mixed with such information as the beginning of a polygon, the end of a polygon and object merge information.
During the renaming phase, the circuit layout is "scanned" in reverse order and the temporary file is read backwards. Thus, for example, the object 7 is read first, and is found to have an associated end of polygon marker. Accordingly, a final polygon name is assigned to the object 7. Further scanning of the layout and processing of the temporary file reveals that the object 7 merges with the object 6. Accordingly, the final number assigned to the object 7 is also assigned to the object 6. When the object 6 is scanned, a beginning-of-node or beginning-of-polygon marker is read from the temporary file and indicates that no other objects are associated with the polygon consisting of the objects 6 and 7. A similar analysis is then performed on the objects 1 through 5, whereby the interrelationship of these objects defines the connectivity associated with the polygon A.
At this point, the information regarding the polygons included in the circuit layout is stored in the output file in reverse order. Thus, as mentioned above, the output file could be written in reverse order to properly identify the objects of the polygons in the order with which they were encountered during the first pass.
The aforedescribed third method of labelling polygons provides greater efficiency than either of the previously described methods. However, because many computer operating systems impose a severe speed penalty when reading a file backwards, one drawback of this labelling process is that it tends to be input/output bound; i.e., it spends time waiting for the next block of data from the computer operating system. This is especially true in the final phase of polygon labelling, wherein the output file is in exactly backwards order. With such an approach, although no processing is required to reverse the file, it still must be read from the end so that the final output may be written from the beginning.
A further drawback of the Szymanski-Van Wyk approach is that it writes all of the input file data to the temporary file, plus polygon start, merge, and ending information. As a result, the temporary file is significantly larger than the input file and thus requires a substantial amount of disk space.
Accordingly, there is a need for a more efficient method of updating object numbers during polygon labelling which would operate more efficiently and cost effectively when two temporary object numbers associated with the same polygon must be reconciled.